package com.biancheng.biancheng.biancheng3;

public class 背包问题 {

    // 问题描述：有n个物品，他们的质量和价值分别为w[i]和v[i]，现在有一个容量为C的背包，要求选择性的放入物品使该背包的价值最大。

    public static void main(String[] args) {
        背包问题 test = new 背包问题();

        // 商品名字数组
        String[] nameArr = {"鞋子", "音响", "电脑"};

        // 商品重量数组
        int[] weightArr = {1/*鞋子*/, 4/*音响*/, 3/*电脑*/};

        // 商品价格数组
        int[] priceArr = {1500/*鞋子*/, 3000/*音响*/, 2000/*电脑*/};

        // 背包容量
        int packageCapacity = 4;

        // 把不可重复的商品装入背包
        test.backpackWithoutRepeat(nameArr, weightArr, priceArr, packageCapacity);
    }




    /**
     * 装入背包
     * @param nameArr 商品名字数组
     * @param w 商品重量数组
     * @param priceArr 商品价格数组
     * @param packageCapacity 背包容量
     */
    private void backpackWithoutRepeat(String[] nameArr, int[] w, int[] priceArr, int packageCapacity) {
        /**
         * 声明一个能装入 0、1、2、3磅......的背包的二维价格表；举例：就好比 v数组是表2的数据
         */
        int[][] v = new int[nameArr.length + 1][packageCapacity + 1];

        // 构建可能装入背包的二维数组
        // 值为0时说明不会装进背包, 值为1说明可能装入背包
        int[][] contentArr = new int[nameArr.length + 1][packageCapacity + 1];

        /**
         * 为什么i一开始是1不是0？看表2的数据，是不是第一行全是0啊
         */
        for (int i = 1; i < v.length; i++) {

            /**
             * 为什么j一开始是1不是0？看表2的数据，是不是第一列全是0啊
             */
            for (int j = 1; j < v[i].length; j++) {

                /**
                 * 文章中当 w[i] > j 时，就有 v[i][j] = v[i-1][j]；
                 * 因为我们程序i是从1开始的，因此原来公式中的w[i]修改成w[i-1]；
                 * 当前商品 > 背包容量, 取同列上一行数据
                 */
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    /**
                     *  当前商品 <= 背包容量, 对两部分内容进行比较;
                     *  第一部分, 该列上一行数据
                     */
                    int onePart = v[i - 1][j];

                    /**
                     * 还记得文章中写的 当j >= w[i] 时，有 v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 这个公式成立吗？
                     * priceArr[i - 1]: 当前商品价格;
                     * w[i - 1]: 当前商品重量;
                     * j - w[i - 1]: 去掉当前商品, 背包剩余容量;
                     * 不可重复: v[i - 1][j - w[i - 1]]: 在上一行, 取剩余重量下的价格最优解;
                     */
                    int otherPart = priceArr[i - 1] + v[i - 1][j - w[i - 1]];

                    /**
                     *  取最大值为当前位置的最优解
                     */
                    v[i][j] = Math.max(onePart, otherPart);

                    /**
                     *  如果最优解包含当前商品, 则表示当前商品已经被使用, 进行记录
                     */
                    if (otherPart == v[i][j]) {
                        contentArr[i][j] = 1;
                    }
                }
            }
        }


        // 不能重复的场景中
        // 如果该位置的标志位为1, 说明该商品参与了最终的背包添加
        // 如果该位置的标志位为0, 即使该位置的价格为最大价格, 也是从其他位置引用的价格
        // 因为不能重复, 所以每行只取一个数据参与最终计算, 并只判断在最大位置该商品是否参与
        // 该最大位置会随着已经遍历出其他元素而对应不断减小, 直到为0


        // 二维数组最后一个元素必然是最大值, 但是需要知道该最大值是自身计算的 还是比较后引用其他的
        int totalPrice = 0;
        // 最大行下标数, 即商品数
        int maxLine = contentArr.length - 1;
        // 最大列下标数, 即重量
        int maxColumn = contentArr[0].length - 1;
        for (;maxLine > 0 && maxColumn > 0;) {
            // 等于1表示在该位置该商品参与了计算
            if (contentArr[maxLine][maxColumn] == 1) {
                // 遍历后, 对重量减少, 下一次从剩余重量中取参与商品
                maxColumn -= w[maxLine - 1];
                totalPrice += priceArr[maxLine - 1];
                System.out.println(nameArr[maxLine - 1] + "加入了背包");
            }
            // 因为不能重复
            // 所以如果该商品参与了背包容量, 则肯定剩余的最大位置处参与,
            // 否则跟该数据无关, 直接跳过
            maxLine--;
        }
        System.out.println("背包可容纳的最大价值: " + totalPrice);
    }



}
